package leetcode.搜索;

/**
 * 搜索插入位置
 *
 * 定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
 * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 你可以假设数组中无重复元素。
 */
public class Test35搜索插入位置 {

    public static int searchInsert(int[] nums, int target) {
//        int ans = 0;
//        int start = 0;
//        int end = nums.length - 1;
//        while (start <= end) {
//            int mid = (end - start) / 2 + start;
//            if (target < nums[mid]) {
//                end = mid - 1;
//            } else if (target > nums[mid]) {
//                start = mid + 1;
//            } else {
//                ans = mid;
//                break;
//            }
//        }
//        // 查找失败返回元素应该被插入的位置
//        for (int i = 0; i < nums.length; i++) {
//            if (target > nums[nums.length - 1]) {
//                ans = nums.length;
//                break;
//            }
//            if (target == nums[nums.length - 1]) {
//                ans = nums.length - 1;
//                break;
//            }
//            if (target <= nums[0]) {
//                ans = 0;
//                break;
//            }
//            if (target > nums[i] && target < nums[i + 1]) {
//                ans = i + 1;
//                break;
//            }
//        }
//        return ans;

        int length = nums.length;
        for(int i = 0; i < length; i++ ){
            if(nums[i] >= target ){
                return i;
            }
        }
        return length;
    }

    public static void main(String[] args) {
        int[] nums = {1};
        int target = 0;
        System.out.println(searchInsert(nums, target));
    }
}
